package 代码随想录_动态规划.完全背包;

/**
 * @author zx
 * @create 2022-05-31 12:17
 * 所以求组合类问题的公式，都是类似这种：
 * dp[j] += dp[j - coins[i]]
 *
 * 1.确定dp数组（dp table）以及下标的含义
 *  dp[j]：凑成总金额j的货币组合数为dp[j]
 * 2.确定递推公式
 *  dp[j] += dp[j - coins[i]];
 * 3.dp数组如何初始化
 *  dp[0]一定要为1，dp[0] = 1是 递归公式的基础。
 *  从dp[i]的含义上来讲就是，凑成总金额0的货币组合数为1。
 * 4.确定遍历顺序
 *  在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。
 *  如果求组合数就是外层for循环遍历物品，内层for遍历背包。
 *  如果求排列数就是外层for遍历背包，内层for循环遍历物品。
 * 5.举例推导dp数组
 *
 */
public class 零钱兑换II_518 {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i = 0;i < coins.length;i++){
            for(int j = coins[i];j <= amount;j++){
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}
